package com.zxy.leetcode._00000_00099._00010_00019;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/3sum/
 *
 * 三数之和
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
 * 使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 *
 * 思路：双指针
 */
public class Test00015 {

    public static void main(String[] args) {
        Test00015 test = new Test00015();

        int[] nums = {-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
        System.out.println(test.threeSum(nums));
    }

    public List<List<Integer>> threeSum(int[] nums) {
        if (nums == null || nums.length < 3) {
            return Collections.emptyList();
        }

        Arrays.sort(nums);

        List<List<Integer>> list = new ArrayList<>(nums.length / 3);

        int a = 1;
        int b = 1;
        int c = 1;

        int i = 0;
        while (i <= nums.length-3) {
            if (nums[i] > 0) {
                break;
            }
            // 跟前面一样的，必然重复
            if (i > 0 && nums[i] == nums[i-1]) {
                i++;
                continue;
            }

            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    if (a == nums[i] && b == nums[j] && c == nums[k]) {
                        // 数据重复
                    }else {
                        List<Integer> tmpList = new ArrayList<>();
                        tmpList.add(nums[i]);
                        tmpList.add(nums[j]);
                        tmpList.add(nums[k]);
                        list.add(tmpList);

                        a = nums[i];
                        b = nums[j];
                        c = nums[k];
                    }
                    j ++;
                    k --;
                }else if (sum > 0) {
                    k --;
                }else {
                    j ++;
                }
            }

            i ++;
        }

        return list;
    }

}
